package JZOffer;

/**
 * 剑指 Offer 39. 数组中出现次数超过一半的数字
 * 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
 * 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
 * **/
//利用哈希表  o(n)  o(n)
//利用排序 o（n log n）   o(1)

//摩尔投票法  o（n）  o(1)
class Solution39 {
    public int majorityElement(int[] nums) {
        //正反抵消原则
        int count = 0, value = -1;

        for (int n : nums) {
            //目的是否有确定的计数目标，若没有，就把当前的设定为目标
            if (count == 0) {
                value = n;
                count = 1;
            }
            //如果计数目标value已经存在，比较计数目标是否等于当前元素
            else if (value == n) {
                count ++;
            }else {
                count --;
            }
        }
        return value;
    }
}